#include <iostream>
#include <cstring>
#include <queue>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e3 + 10, M = 1e5 + 10;

int h[N << 1], e[M << 1], ne[M << 1], w[M << 1], idx;

int dist[N << 1];
bool st[N << 1];

int n, m;

void add(int a, int b, int c)
{
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dijkstra(int s)
{
	priority_queue<PII, vector<PII>, greater<PII>> heap;
	
	memset(dist, 0x3f, sizeof dist);
	
	heap.push({0, s});
	dist[s] = 0;
	
	while (heap.size())
	{
		PII a = heap.top(); heap.pop();
		
		if (st[a.y]) continue;
		
		st[a.y] = true;
		
		for (int i = h[a.y]; ~i; i = ne[i])
		{
			int j = e[i];
			
			if (dist[j] > dist[a.y] + w[i])
			{
				dist[j] = dist[a.y] + w[i];
				heap.push({dist[j], j});
			}
		}
	}
	
	
}

int main()
{
	cin >> n >> m;
	
	memset(h, -1, sizeof h);
	
	while (m -- )
	{
		int a, b, c;
		cin >> a >> b >> c;
		
		add(a, b, c);
		add(b + n, a + n, c);
		
	}
	
	LL res = 0;
	
	dijkstra(1);
	
	for (int i = 1; i <= n; i ++ ) res += dist[i];
	
//	for (int i = 1; i <= n; i ++ ) cout << dist[i] << endl;
	
	dijkstra(1 + n);
	
	for (int i = 1 + n; i <= 2 * n; i ++ ) res += dist[i];
	
	cout << res << endl;
	
	return 0;
}